Problem statement: zenit16ckh

Hypotéka

Počet bodov: 25, časový limit: 1000ms

Keď Ondrej od kamaráta počul, ako super sa dá zarobiť prenájmom bytu, nadšený si hneď zobral hypotéku a nejaký kúpil. Aby sa aj on neskôr mohol chváliť svojim kamarátom, každý mesiac si poctivo zaznamenával všetky výdavky hocijako spojené s bytom (hypotéka, nájom, opravy, …).

S nejakým časovým odstupom mu je jasné, že niektoré mesiace boli lepšie, niektoré horšie. Niekedy do bytu nevedel nikoho dostať, inokedy zase ľutoval, že nekúpil väčší byt. Niekedy platil iba elektrinu, inokedy musel premaľovať a dať do opravy práčku aj mikrovlnku v jednom mesiaci.

Ako tak pozerá na svoje celkom dlhé záznamy, chce si overiť pár údajov pred tým, ako sa pôjde pochváliť kamarátom. Chce zistiť, prečo nastali všetky také momenty, že mal zrazu dokopy menej peňazí z bytu ako niekedy v minulosti. Aby vedel začať, poraďte mu, kedy sa prvýkrát niečo také stalo.

Úloha

Máte zadané Ondrejove záznamy. Záznam v danom mesiaci predstavuje celkovú bilanciu na konci toho mesiaca. Na začiatku si Ondrej zobral hypotéku, teda nultý mesiac nikdy zisk nemá, je vždy v mínuse. Nájdite najmenšiu takú dvojicu mesiacov \(x < y\), že bilancia v mesiaci \(x\) je väčšia ako bilancia v mesiaci \(y\).

Vstup a výstup

Na prvom riadku je číslo \(1 \leq n \leq 100\,000\) – počet mesiacov, o ktorých máme záznam bilancie.

Na nasledujúcom riadku sú postupne bilancie \(b_0 \cdots b_{n-1}\) v týchto mesiacoch. Každá bilancia je celé číslo, ktoré v absolútnej hodnote neprevyšuje \(10^{12}\). Hodnota \(b_0\) predstavuje veľkosť hypotéky (keďže je to výdavok, je v zápore).

Zo všetkých usporiadaných dvojíc mesiacov \((x, y)\), kde \(x < y\) a \(b_x > b_y\) nájdite lexikograficky najmenšiu a tú vypíšte. Teda pre najmenšie \(x\) vypíšte najmenšie \(y\), ktoré spĺňa podmienky. Ak takáto dvojica neexistuje, vypíšte -1.

 Príklad

Input:

6
-2 1 2 4 5 3

Output:

3 5

Zoberiem si lacnú dvojeurovú hypotéku. Už v prvý mesiac 3 eurá zarobím a tak moja bilancia zostane na 1 eure. Stále mám pravidelný príjem, až keď zrazu v 5. mesiaci som musel nakomplet prerobiť byt a dostal som sa tak na bilanciu, ktorú by som čakal niekedy okolo 3. mesiaca. Inými slovami, od 3. do 5. mesiaca som nič nezarobil. Ľahko možno overiť, že dvojica \((3, 5)\) ozaj spĺňa zadanie.

Input:

3
-10 -5 100

Output:

-1

Všetko je v poriadku, stále len zarábam.

Input:

10
-2 3 -3 2 6 -4 1 -5 5 -2

Output:

0 2